#include <iostream>
using namespace std;
class MinHeap {
  private:
    int *heapArray;
    int CurrentSize;
    int MaxSize;
    void BuildHeap(int n);

  public:
    MinHeap(const int n, const int *a);
    virtual ~MinHeap();
    bool isLeaf(int pos) const;
    int leftchild(int pos) const;
    int parent(int pos) const;
    bool Remove(int pos, int &node);
    bool Insert(const int &newNode);
    void RemoveMin(int &min_val);
    void SiftUp(int position);
    void SiftDown(int position);
    void show();
    void sort();
};
MinHeap::MinHeap(const int n, const int *a) {
    CurrentSize = n;
    MaxSize = CurrentSize + 10;
    heapArray = new int[MaxSize];
    int i = 0;
    for (int i = 0; i < n; i++)
        heapArray[i] = a[i];
    BuildHeap(CurrentSize);
}
MinHeap::~MinHeap() { delete[] heapArray; }
void MinHeap::SiftDown(int position) {
    int i = position;
    int j = 2 * i + 1;
    int temp = heapArray[i];
    while (j < CurrentSize) {
        if (j < CurrentSize - 1 && heapArray[j] > heapArray[j + 1])
            j++;
        if (temp > heapArray[j]) {
            heapArray[i] = heapArray[j];
            i = j;
            j = 2 * j + 1;
        } else
            break;
    }
    heapArray[i] = temp;
}
void MinHeap::BuildHeap(int n) {
    CurrentSize = n;
    for (int i = CurrentSize / 2 - 1; i >= 0; i--) {
        SiftDown(i);
    }
}
void MinHeap::SiftUp(int position) {
    int temppos = position;
    int temp = heapArray[temppos];
    while ((temppos > 0) && (heapArray[parent(temppos)] > temp)) {
        heapArray[temppos] = heapArray[parent(temppos)];
        temppos = parent(temppos);
    }
    heapArray[temppos] = temp;
}
bool MinHeap::Remove(int pos, int &node) {
    if ((pos < 0) || (pos >= CurrentSize))
        return false;
    int temp = heapArray[pos];
    heapArray[pos] = heapArray[--CurrentSize];
    if (heapArray[parent(pos)] > heapArray[pos])
        SiftUp(pos);
    else
        SiftDown(pos);
    node = temp;
    return true;
}
int MinHeap::parent(int pos) const { return pos / 2; }
void MinHeap::RemoveMin(int &min_val) {
    min_val = heapArray[0];
    for (int i = 1; i < CurrentSize; i++)
        heapArray[i - 1] = heapArray[i];
}
bool MinHeap::isLeaf(int pos) const {
    if (pos * 2 + 1 >= CurrentSize)
        return true;
    else
        return false;
}
int MinHeap::leftchild(int pos) const {
    if (pos * 2 + 1 < CurrentSize)
        return pos * 2 + 1;
}
bool MinHeap::Insert(const int &newNode) {
    if (CurrentSize == MaxSize)
        return false;
    heapArray[CurrentSize] = newNode;
    SiftUp(CurrentSize);
    CurrentSize++;
}
void MinHeap::show() {
    for (int i = 0; i < CurrentSize; i++)
        cout << heapArray[i] << " ";
    cout << "\n";
}
void MinHeap::sort() {
    int min_val;
    for (int i = CurrentSize; i > 0; i--) {
        BuildHeap(i);
        RemoveMin(min_val);
        cout << min_val << " ";
    }
    cout << "\n";
}
int main() {
    int a[] = {72, 23, 5, 68, 94, 16, 71, 84, 76};
    MinHeap m = MinHeap(9, a);
    //    m.Insert(63);
    m.show();
    //    m.sort();
}
